package xyz.scootaloo.draft.textbook.chapter3;

/**
 * @author flutterdash@qq.com
 * @since 2021/5/31 12:43
 */
public class P5 {

    public static void main(String[] args) {
        // 限制: 最多只求到100以内的素数
        final int limit = 100;

        // 使用一个布尔数组来存放标记过的位置
        // 被标记过的位置不是素数
        boolean[] mark = new boolean[limit + 1];

        // 1 是第一个素数, 所以接下来从 2 开始计算
        System.out.println(1);

        for (int i = 2; i<=limit; i++) {
            if (mark[i]) {
                continue; // 不是素数, 直接跳过
            } else {
                System.out.println(i); // 是素数, 输出这个结果
                // 为什么有这个循环?
                // 一个质数, 例如2, 任何数乘它都不是质数, 例如 4, 6, 8, 10, 12, 14, 16 ...
                // 标记出这些位置, 减少计算量
                for (int j = i; j * i <=limit; j++)
                    mark[j * i] = true;
            }
        }
    }

}
